package com.utils;

public class AVLNode01 {


        /** 数据 **/
        public Map data;
        /** 相对高度 **/
        public int height;
        /** 父节点 **/
        public AVLNode01 parent;
        /** 左子树 **/
        public AVLNode01 left;
        /** 右子树 **/
        public AVLNode01 right;
        public AVLNode01(Map data) {
            this.data = data;
            this.height = 1;
        }


    /** 通过子树高度 计算高度 **/
    private int calcHeight(AVLNode01 root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.right == null) {
            return root.left.height + 1;
        } else if (root.left == null) {
            return root.right.height + 1;
        }else {
            return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
        }
    }


    /**
     * 计算 BF
     * BF（平衡因子）的值为：左子树高度 - 右子树高度
     * @param root
     * @return
     */
    private int calcBF(AVLNode01 root) {
        if (root == null){
            return 0;
        }
        else if (root.left == null && root.right == null) {
            return 0;
        }
        else if (root.right == null) {
            return root.left.height ;
        } else if (root.left == null) {
            return - root.right.height;
        }else {
            return root.left.height - root.right.height;
        }
    }


    /**
     * 左旋
     * 旧根节点为新根节点的左子树
     * 新根节点的左子树（如果存在）为旧根节点的右子树
     * @param root
     * @return
     */
    public AVLNode01 leftRotate(AVLNode01 root) {
        AVLNode01 oldRoot = root;
        AVLNode01 newRoot = root.right;
        AVLNode01 parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data.getLinkID() > oldRoot.data.getLinkID()) {
                parent.left = newRoot;
            }else  {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的左子树 给 oldRoot 的右子树)
        oldRoot.right = newRoot.left;
        if (newRoot.left != null) {
            newRoot.left.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.left = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }

    /**
     * 右旋：
     * 旧根节点为新根节点的右子树
     * 新根节点的右子树（如果存在）为旧根节点的左子树
     * @param root
     * @return
     */
    public AVLNode01 rightRotate(AVLNode01 root) {
        AVLNode01 oldRoot = root;
        AVLNode01 newRoot = root.left;
        AVLNode01 parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data.getLinkID() > oldRoot.data.getLinkID()) {
                parent.left = newRoot;
            }else {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的右子树 给 oldRoot 的左子树)
        oldRoot.left = newRoot.right;
        if (newRoot.right != null) {
            newRoot.right.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.right = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }






}
